\section{The Problem Definition}\label{sec:problem}


\begin{figure}
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.4\textwidth]{fig/designspace.pdf}
  \caption{The design space of a module in high-level synthesis}\label{fig:designspace}
  \vspace{-10pt}
\end{figure}


This section introduces preliminaries on high-level synthesis and 3D physical
planning, and then presents the problem formulation of this paper.

\subsection{High-Level Synthesis}

High-level synthesis (HLS) is the process of translating a behavioral
description into a register level structure description. Scheduling and
resource binding are key steps during the synthesis process. The scheduler is
in charge of sequencing the operations of a control/data flow graph (CDFG) in
correct order and it tries to schedule as many operations as possible in the
same control step to extract more parallelism. The binding process binds
operations to hardware units in the resource library to complete the mapping
from abstracted descriptions of circuits into practical designs.

The resource library consists of hardware units with different delay and area
properties, which make it possible to perform design exploration to get more
optimized result during the synthesis process. Figure~\ref{fig:designspace}
shows the design space exploration for a specific module used in high-level
synthesis. \texttt{ARCH I-III} denotes different architectural implementations
of the module with the same functionality, while the black squares inside each
architecture shows the design points with different module-level and circuit-level optimizations
(multi-Vth/Vdd, gate sizing, \emph{etc}.), which lead to different delay and
power values of the same architecture. Therefore, given the delay constraint
shown in Figure~\ref{fig:designspace}, there are two architectures available
and each architecture has two viable design options. The synthesis tool can
choose between these options for a best fit of all design considerations.



\subsection{3D Physical Planning}

Physical planning is a key step in 3D IC design. It usually involves layer
assignment and floorplanning of modules on each layer. Layer assignment, which
is unique in 3D IC design, assigns blocks and modules to different layers in
order to balance the area split, to mitigate the thermal crisis, as well as to
reduce the interconnect wirelength.
Figure~\ref{fig:3dfp} shows the physical planning process for a 3D microprocessor. During the planning process, modules can be moved around within a layer as well as between layers, to achieve the best performance in terms of delay/power/area/\emph{etc}. A coarse-grain physical planning methodology can generate balanced assignment and placement of modules at the early stage of the design process, and provide confidence and guidance for the succeeding design steps.

\begin{figure}
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.3\textwidth]{fig/3dfp.pdf}
  \caption{3D physical planning including layer assignment and floorplanning}\label{fig:3dfp}
  \vspace{-10pt}
\end{figure}


\subsection{Problem Formulation}
During 3D physical planning, several operations can be performed to change the
location, layer assignment and aspect ratio of any module. However, the
delay/power/area of such modules are fixed, leading to a limited design space.
Meanwhile, high-level synthesis can generate architectures and design points of
a give specification with different delay/power/area values. Therefore, if
high-level synthesis can be incorporated into the physical planning process,
the design space will be significantly enlarged and the quality of the design
decision will be greatly improved. With high-level synthesis as a tuning knob
of each module in the design, a framework with two levels of optimization
loops can be established, in which the physical planning serves as the outer
loop and evaluates all potential movements, and high-level synthesis acts as a
fine tuning tool to facilitate the movements. Within such a framework, several
design considerations including performance, process variability and thermal
efficiency of 3D ICs can be effectively addressed:

\subsubsection{Mitigating the Impact of Process Variations}

\begin{figure}
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.45\textwidth]{fig/adder.pdf}
  \caption{The delay variation for 16-bit adders in IBM Cu-08 technology
(Courtesy of IBM).}\label{fig:adder}
\vspace{-10pt}
\end{figure}


CMOS process variability is a major challenge in deep-submicron SoC designs.
The variations in transistor parameters are complicating both timing and power
consumption prediction. Previous work has shown that different architectural
implementations of the same function modules, might have different immunity to
process variability~\cite{Chen10}. As shown in Fig.~\ref{fig:adder}, the
normalized delay variability varies with different adder architectures.
Consequently, architectural components such as ALU will exhibit similar
behavior when they are built up with these circuit modules. Therefore, besides
delay and power, the variability becomes a new metric to explore and to
optimize during higher levels of the design hierarchy.

Researchers have then proposed optimization techniques in behavioral or
high-level synthesis to reduce the variability of synthesized results, with the
price of increased power or silicon area~\cite{HLS:Jung07, HLS:Wang082,
HLS:Greg09}. These techniques can mitigate the impact of process variations at
the early stage of a design flow. However, most of these optimizations are
physical-unaware -- the work on high-level is unable to address the impact of
interconnects and spatial correlations of process variability. Combining
high-level synthesis and physical planning will lead to an effective way to
address the process variability of 3D ICs. In our proposed framework, after the
initial physical planning is done, the interconnect delays are extracted and
the process variations of all components are re-evaluated with the updated
spatial correlations. With such information, the near-critical components can
be identified, and HLS is then called to optimize such modules to reduce the
variability. The optimization will result in alternatives with different
power/area, and these may violate the delay/power/thermal constraints so a new
iteration of physical planning is required.

To bring the process-variation awareness to the high-level synthesis flow, we
first introduce a new metric called \emph{Parametric Yield}. The parametric
yield is defined as the probability of the synthesized hardware meeting a
specified constraint $Yield = P(Y \leq Y_{max})$, where $Y$ can be delay or
power. We assume that each architectural blocks are separately by registers.
Given the clock cycle time $t_{CLK}$, the timing yield of the entire system,
$Yield_{t}$ is defined as:
\begin{equation}\label{eq:tyield}%\scriptsize
Yield_{t}=P(t_1 \leq t_{CLK}, t_2\leq t_{CLK},\ldots,t_n\leq t_{CLK})
\end{equation}
where $P()$ is the probability function, $t_1, t_2,\ldots,t_n$ are the arrival
time distributions of each architectural block $B_1, B_2,\ldots,B_n$,
respectively.

In each iteration, we use the model presented in~\cite{PV:ABZ03} to model the
spatial correlations of the process variability. As shown in
Fig.~\ref{fig:pvmodel}, an independent random variable $L_{l,r}$ is associated
with each region $(l, r)$ to represent a component of the total process
variation. The total intra-die variation of a given block will be the sum of
$L_{l,r}$ variables corresponding to the $(l,r)$ regions that intersect with
the block. Such spatial correlations are then fed to a gate-level statistical
timing analysis tool to recalculate the yield of each architectural block.

\begin{figure}
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.3\textwidth]{fig/pvmodel.pdf}
  \caption{The process variability model with spatial correlation~\cite{PV:ABZ03}.}\label{fig:pvmodel}
  \vspace{-10pt}
\end{figure}


\subsubsection{Improving Thermal Efficiency}
Heat dissipation is one of the key challenges in the design of 3D ICs, due to
the stacking of multiple active layers and the improved logic density.
Therefore, the thermal efficiency problem has to be addressed from the very
beginning of the 3D IC design. In our proposed physical planning framework, a
temperature estimator could be integrated into the flow to evaluate the
temperature profile of the design after any optimistic move. At each
iteration, the framework will identify the modules with hot spots. Such modules
will be moved around the chip for a better head conduction or be replaced with
their alternatives. At this point, the design space of such modules could be
explored, and candidates with lower power consumption, thus lower heat
dissipation could be chosen as the replacement. After the movement or
replacement of these critical modules, a new iteration will be initiated to
optimize the other modules in order to meet the design constraints.

For quick temperature estimation, we model 3D ICs as resistor-capacitor
structures in a thermal RC model similar to~\cite{Huang2006}. For a
microarchitectural unit, heat conduction to the thermal package and to
neighboring units are the dominant mechanisms that determine the temperature.
The RC model consists of a vertical and a lateral convection model.
Figure~\ref{fig:tsvfarmblock} shows the block level RC modeling, where each
modules is modeled as a block with its power dissipation and thermal
resistance. The vertical thermal resistance ($R_V$) captures heat flow from one
layer to the next, moving from the source die through the package. The lateral
thermal resistance ($R_L$) captures heat diffusion between adjacent blocks
within a layer, and from the edge of one layer into the periphery of the next
area. The temperature of each block can then be estimated as:
\begin{equation}\label{eq:temp}
\scriptsize
\left[ \begin{array}{c}
T_1 \\
T_2 \\
\vdots \\
T_n
\end{array} \right]
=
\left[ \begin{array}{cccc}
R_{11} & R_{12} & \ldots & R_{1n}\\
R_{21} & R_{22} & \ldots & R_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
R_{n1} & \ldots & \ldots & R_{nn} \\
\end{array} \right]
\times
\left[ \begin{array}{c}
P_1 \\
P_2 \\
\vdots \\
P_n
\end{array} \right]
.
\end{equation}
where $T_{1\ldots n}$ and $P_{1\ldots n}$ denotes the temperature and power
consumption values for blocks $1\ldots n$, respectively. $\mathbf{R}=R_{1\ldots
n,1\ldots n}$ is the transfer matrix built from $R_V$ and $R_L$ of each block.

\begin{figure}
\centering
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.3\textwidth]{./fig/tsvfarm.pdf}\\
  \caption{Block mode thermal RC modeling for 3D ICs.}\label{fig:tsvfarmblock}
  \vspace{-10pt}
\end{figure}

 With the proposed fast temperature estimator, the physical planning flow
is able to address the thermal issue by iteratively identifying the hot spots
and optimizing the corresponding modules through design space exploration,
creating a balanced thermal profile for the whole IC stack.

\vspace{10pt}
